public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = new int[]{1,3,2,3,1};
        System.out.println(s.reversePairs(nums));
    }

    public int reversePairs1(int[] nums) {
        /**
         * 翻转对
         * 解法1：暴力求解
         * 注意问题1：数据可能超大，因此比较时使用long类型*/
        // 1 预处理
        int n = nums.length;

        // 2 暴力查找
        int answer = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                if((long)nums[i] > (long)2*nums[j]) {
                    answer ++;
                    System.out.println("元素：" + nums[i] + " " + nums[j]);
                    System.out.println("下标：" + i + " " + j);
                    System.out.println("----------");
                }
            }
        }

        // 3 返回值
        return answer;
    }

    public int reversePairs(int[] nums) {
        /**
         * 翻转对
         * 解法2：归并排序（计数逻辑允许）
         * 注意问题：
         *      1，数据可能超大，因此比较时使用long类型
         * 使用策略
         *      当前元素cur后面有多少小于cur/2的元素（降序）
         * 解题步骤：
         *      1，分别计算a、b
         *      2，联合a、b计数*/
        return mergeSort(0, nums.length-1, nums);
    }

    public static int[] tempArray = new int[5_0000];

    public static int mergeSort(int left, int right, int[] nums) {
        /**
         * 归并排序解决计数问题*/
        // 1 递归出口
        if(left >= right) {
            return 0;
        }

        // 2 分别计算左右区间
        int answer = 0;
        int mid = left + (right - left) / 2;
        answer += mergeSort(left, mid, nums);
        answer += mergeSort(mid + 1, right, nums);

        // 3 合并a、b区间计算
        int baseIndex = left;
        int n = right - left + 1;
        // -先利用左右区间有序计算翻转对（同向双指针不回退）
        int l1 = left;
        int l2 = mid + 1;
        while(l1 <= mid && l2 <= right) {
            if((long)nums[l1] <= 2L*nums[l2]) {
                l2++;
            } else {
                answer += (right-l2+1);
                l1++;
            }
        }
        // -临时写入
        int left2 = mid + 1;
        int tempIndex = 0;
        while(left <= mid && left2 <= right) {
            if(nums[left] < nums[left2]) {
                tempArray[tempIndex++] = nums[left2++];
            } else {
                tempArray[tempIndex++] = nums[left++];
            }
        }
        while(left <= mid) {
            tempArray[tempIndex++] = nums[left++];
        }
        while(left2 <= right) {
            tempArray[tempIndex++] = nums[left2++];
        }
        // -真实写入
        for(int i = 0; i < n; i++) {
            nums[baseIndex + i] = tempArray[i];
        }

        // 4 返回值
        return answer;
    }
}
